JZ64 滑动窗口的最大值

https://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788

注意这题不适合使用堆来解，看很多题解都是利用了大根堆的 remove(object) 这个方法去删除元素，但是这个方法本身就是 $log(n)$ 的，所以实际和暴力法区别不大（甚至更慢）

第一次解：

暴力法

import java.util.*;

public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> result = new ArrayList<>();
        if (num == null || num.length < 1 || size < 1 || num.length < size) return result;
        
        // 这题使用双指针的做法
        int low = 0; // 这个只是计数用
        int high = 0; // 移动 size 次
        while (high + size <= num.length) {
            int max = num[low];
            for (int i = high; i < high + size; i++) {
                if (num[i] > max) max = num[i];
            }
            low++;
            high = low;
            result.add(max);
        }
        
        return result;
    }
}

这个是最坏的时间复杂度 $O(size * num.length)$

第二次解：

使用双端队列

一个滑动窗口实际上可以看成一个队列。当窗口滑动时，处于窗口第一个位置的数字被删除，同时在窗口的末尾又增加了一个新的数字。这符合队列“先进先出”的特性。

使用双端队列。我们不把所有的值都加入滑动窗口，而是只把有可能成为最大值的数加入滑动窗口。这就需要一个两边都可以操作的双向队列。

我们以数组 {2,3,4,2,6,2,5,1} 为例，滑动窗口大小为 3，先把第一个数字 2 加入队列，第二个数字是3 ，比 2 大，所以 2 不可能是最大值，所以把 2 删除，3 存入队列。第三个数是 4，比 3 大，同样删 3 存 4，此时滑动窗口以遍历三个数字，最大值 4 在队列的头部。

第四个数字是 2，比队列中的数字 4 小，当 4 滑出去以后，2 还是有可能成为最大值的，因此将 2 加入队列尾部，此时最大值 4 仍在队列的头部。
第五个数字是 6，队列的数字 4 和 2 都比它小，所以删掉 4 和 2，将 6 存入队列尾部，此时最大值 6 在队列头部。
第六个数字是 2，此时队列中的数 6 比 2 大，所以 2 以后还有可能是最大值，所以加入队列尾部，此时最大值 6 在仍然队列头部。 ······

依次进行，这样每次的最大值都在队列头部。

还有一点需要注意的是：如果后面的数字都比前面的小，那么加入到队列中的数可能超过窗口大小，这时需要判断滑动窗口是否包含队头的这个元素，为了进行这个检查，我们可以在队列中存储数字在数组中的下标，而不是数值，当一个数字的下标和当前出来的数字下标之差大于等于滑动窗口的大小时，这个元素就应该从队列中删除。

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> result = new ArrayList<>();
        if (num == null || num.length < 1 || size < 1 || num.length < size) return result;
        
        ArrayDeque<Integer> maxQueue = new ArrayDeque<>();
        for(int i = 0; i < num.length; i++) {
            // 令当队列呈递减
            while (!maxQueue.isEmpty() && num[maxQueue.peekLast()] < num[i]) {
                maxQueue.pollLast(); // 丢掉小的
            }
            maxQueue.addLast(i);
            if (maxQueue.peekFirst() == i - size) {
                maxQueue.pollFirst(); // 当前队头的元素过期了
            }
            // 完整的走过一次滑动窗口就可以开始填入最大值了
            if (i >= size - 1) {
                result.add(num[maxQueue.peekFirst()]);
            }
        }
        
        return result;
    }
}